---
title: "最优包含"
created: 2025-11-28
tags:
  - 算法
---

# 最优包含

## 题目 [最优包含](https://www.lanqiao.cn/paper/3845/problem/239/)

![[image-03e3b493.png]]

## 思路分析

好像是线性dp里的编辑距离的模板

对序列a进行修改使其变成序列b 但这里更复杂 并不是等于序列b 而是包含序列b

![[image-12e8c4fc.png]]

## 代码实现

```cpp
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

typedef long long ll;
const int N = 1e3+5;
const int INF = 0x3f3f3f3f;
int f[N][N]; // f[i][j] : 修改s中多少字符, s[1~i] 包含 t[1~j]

int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    string s, t;
    cin>>s>>t;
    int n=s.size(),m =t.size();
    s = "#" + s; t = "#" + t;

    memset(f,0x3f,sizeof f);//求最小 初始化inf
    for (int i = 0; i <= n; i++)
        f[i][0] = 0; //s的前i个字符包含t的0个字符需要的代价为0

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            if (s[i] == t[j]) {
                f[i][j] = f[i - 1][j - 1];
            } else {
                // 如果s[i] != t[j]
                // 要么花费代价1, 使得s[i] == t[j]
                // 要么只使用s的前i-1个字符包含
                f[i][j] = min(f[i - 1][j], f[i - 1][j - 1] + 1);
            }
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[路径计数|路径计数]] 🏠 [[00-冲刺国赛]] ➡️ [[排列数|排列数]]